大学招生与婚姻的稳定性
2012年10月15日，瑞典皇家科学院诺贝尔奖评审委员会宣布将2012年诺贝尔经济学奖授予哈佛大学教授阿尔文·罗思和加州大学劳埃德·沙普利，以鼓励他们在“稳定匹配理论及市场设计实践”上所作的贡献。而这是关于一些特殊市场的‘配对’问题，所谓“特殊市场”是指除了经济学原理在发挥作用之外，还受到社会、道德、法律等多重因素共同影响的市场，其资源配置更复杂，需要不断优化完善市场设计，比如医学上的器官移植、高校招生、婚姻市场等。经济学奖公布后，学术界指出，沙普利与盖尔在1962年发表的著作 《高校招生与婚姻稳定性》反映了“稳定匹配理论”的最典型应用。
2012年沙普利荣获诺贝尔奖
当年，沙普利与同事戴维·盖尔以10名男子和10名女子“婚配”为范例，设想如果由每一名女子先作选择并向最中意男子“求婚”，然后再由每一名男子审视所获所有“求婚”并回绝除了最中意女子以外的其他所有“求婚”，就可以实现稳定分配；延迟接受算法可以从一对一双边市场（婚姻市场）拓展到一对多双边市场（学校招生）。短短八页《高校招生与婚姻稳定》提供了一个不需要任何公式进行证明的稳定解决方式。在最初因为论文过于简单遭到了两次拒绝之后，在1962年这篇论文终于获得发表。在50年之后的2012年，夏普利因“稳定的分配理论和市场设计实践”荣获诺贝尔经济学奖。
也有人将“稳定匹配理论”简单比喻为备胎算法：你情我愿 > 我情你随便 > 你情我随便 > 不情不愿！今天我们介绍《高校招生与婚姻稳定》中文版供读者参考。
简介
从开始的大学入学问题，到最后讨论婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。
从开始的大学入学问题，到最后讨论 婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。务实的读者大概会马上问，我们有没有做一些努力，来解决现实中的问题。虽然，要回答这个问题，需要考虑许多非数学的因素，而且这种讨论在数学期刊上似乎不太适宜，我们的观点是，我们在这里介绍的观点，可能会被利用于解决某个阶段的入学问题。
我们研究的问题和下面这种典型情况有关：一个大学正在对n个提出申请的学生进行考核，招生的名额是q。在评估申请学生的资格之后，招生处得决定 招收哪些学生。如果仅仅录取q个最具资格的学生，可能达不到令人满意的结果，因为收到录取通知的q个学生不一定都会接受录取。因此，为了使大学能够招收到 q个学生，一般来说，发出的录取通知需要超过q个。解决招收多少学生以及招收哪些学生的问题，需要加入一些猜想。
我们可能并不知道，一个收到录取通知的学生是否还申请了别的学校；即使知道了这一点，也无法搞清楚这个学生对自己申请的学校怎样排名，就算知道了，也难以知道其他哪些学校会愿意招收这个学生。基于种种不确定因素，学校只能期望招进的学生人数和理想的人数接近，并且学生质量能接近可达到的最优值。
通常的招生程序给申请的学生和学校都带来一些困扰。被要求在申请表格中按偏好列出学校排列的学生，可能会觉得如果让一个学校知道它只是自己的第三选择，会降低自己被这个学校录取的可能性。
有个精心设计的方案是引入“候补申请人”名单，意思就是申请者在得知自己没有被录取的同时，也被告知当有空缺存在时可能会被录取。但是，这会导致新的问题。假设一个学生被一所大学录取，与此同时，他又被列在另一所自己更心仪的大学的“候补申请人”名单上，他是应该保险起见，接受第一个大学的录 取，还是冒险一试，寄希望于自己更喜欢的学校呢？如果接受了第一个学校的录取，不告知第二个学校，等第二个学校愿意录取自己时再拒绝第一个学校，这样做道德吗？
上面列出的问题其实都可以避免，我们将描绘一种能令学校和学生两方都满意的分配申请者的程序，这种程序可以清除一切不确定性，并且，假定有足够的申请者，这个程序可以让每个学校分配到和给定招生名额一致的学生。
分配规则
假设，n个申请者将被分配到m个学校，而q是第i个学校的招生名额。每个学生剔除那些在任何情况下都不愿意去的学校，按照自己的偏好对剩下的学校进行一个排名。方便起见，假设学生和学校之间没有关系，那么，即使对于一个学生来说，某两所学校或者多所学校之间没有什么差别，他还是要按照某一顺序给 学校做出排名。每个学校同样按照自己的偏好，给申请者排名，首先排除那些在任何情况下（即使这意味着招生名额不满）都不愿意接收的学生。通过学校的录取名额、学生和学校各自的排列名单，我们希望能够找到某种达成统一意见的公平规则，将申请者分配到学校。
照刚才的思路，简单地看，解决方案很容易浮出水面。不过，很少有人将分配和偏好联系在一起，一旦考虑这点，复杂性就增加了。
举一个简单的案例，假设有两个学校A和B，两个申请者a和b。a更喜欢A学校，b更喜欢B学校，遗憾的是，A学校更喜欢b申请者，B学校更喜欢 a申请者。这种情况下，没有能使各方都满意的分配方案。遇到这种情况，我们又必须做出决定。哲学上，学校是为学生而存在的，而不是反过来。将a申请者分配 到A学校，b申请者分配到B学校这种做法可能是合适的。这也暗示了一个受到承认的大致规则：当其他因素一样时，比起学校，学生应该被优先考虑。这个规则本 身来讲没有什么作用，不过我们讲述完另一个更为明确的事情之后，再回过头来说。
我们接下来要阐述的核心观点就是，无论最终是决定使用哪种分配方案，下面这个定义描述的情况，很有可能不发生。
定义：如果有两个申请者a和b，分别被分配到A学校和B学校，但是b更偏好A学校，而a更偏好B学校，那么，这种分配被定义为“不稳定”。
假定，刚提到的这种情况真的发生了。申请者b可以向A学校表明态度说，自己愿意转到A学校，A学校可以许诺招收申请者b，同时，让a学生转校， 来维持总招收的人数在招生名额之内。A学校和b学生会考虑这么做，让分配更利于各自。如此一来，原来的分配就“不稳定”了，这种分配可能会被学校和申请者 联合推翻，以达到一种对两者都更有好处的分配。
我们对一个分配方法的首个要求，是不会表现出不稳定。这立马就引出一个数学问题：是否总有可能找到一个这样的分配方案？下面我们会给出一个肯定的答案，虽然说，找到佐证的例子并不困难，不过，如有些例子所暗示的，结果看似不那么明显。
假定稳定分配方案暂时存在，我们仍必须决定在诸多可能的稳定方案中，更倾向于哪种。现在，说回到刚刚我们提到的哲学原则，并给它一个确切的表达方式。
定义：如果每个申请者对当前的稳定分配方案的满意度，至少跟对其他稳定分配方案的满意度一样，那么这种稳定分配可被称作“最优”。
稳定分配的存在，远不能说明最优分配就存在，不过，有一点很清楚，最优分配是独一无二的（假使它存在）。如果有两个最优分配，那么，至少有一个申请者，会在其中一种分配方案里，感觉比另一个分配方案里更好，因而这两个所谓最优的分配方案中，有一个说到底就不是最优的了。当我们不考虑存在与否这个 问题，稳定性和最优的规则，能引导我们找到一个独特的“最好”的分配方案。
稳定分配和婚姻问题
在试图解决稳定分配的存在问题的过程中，我们首先想研究一个特别的案例，在这个案例中，申请者和学校的数量一致，而且每个学校的招生名额也统一。当然，这种情况，于实际的学校招生情况来说，是反常的。但是，有另一个“故事”，就可以很符合我们的设想条件。
某一个社区由n个男子和n个女子组成，每个人按照婚姻伴侣的标准，根据自己的偏好，给异性做出排序。我们试图找到一个令人满意的方式，能让社区里的男子和女子都找到伴侣。
模拟之前我们给“不稳定分配”定义，如果在某种分配方案里，一个女子和一个男子没有结婚，但是，对彼此的喜好超过对他们各自的实际伴侣，那么，我们可以说，这种婚姻“不稳定”（这个术语在此很清晰）。
问题：对于各种模式的偏好，是否可能找到一种稳定的婚姻配对？
在给出答案之前，我们先看一些例子。
这个矩阵的每对数字中，第一个数字表示男子对女子的排列，第二个字数表示女子对男子的排列。在这个排列矩阵中，可以发现，男子α将女子A排在第一，女子B在第二，女子C在第三，而女子A将男子β作为首选，γ作为第二选择，α作为第三选择等等。
这个例子里，有6种可能的婚姻配对，其中，有3种配对是稳定的。其中一种达到稳定配对的方法，是让每个男子能娶到自己的最心仪对象，也就是说， 男子α娶女子A，男子β娶女子B，男子γ娶女子C。你也许注意到，每个女子只能嫁给自己的第三选择，然而这种安排是稳定的配对。另一种稳定配对可能是让每个女子嫁给自己最心仪的对象，让C女子嫁给α男子，A女子嫁给β男子，B嫁给γ男子。第三种稳定配对的方案则是，让每个人和自己的第二选择结婚，让α男子 和B女子结婚，β男子和C女子结婚，γ男子和A女子结婚。读者们会很容易证明其他种配对都是不稳定的。
这个矩阵中画了圈的项，显示只有一种稳定的婚姻配对。注意在这种情况下，如果想达到稳定性，每个人都不能够和自己的最心仪对象结婚。
例3．和婚姻配对问题类似的一个问题是“室友分配问题”。比如，有偶数个男孩要被分配成一对对室友。如果分配之后，没有男孩找不到室友，并且也不会存在一个男孩比起和现有室友一起住，更愿意和别的男孩一起住的情况，那么，这种分配可以说是“稳定的”。
举一个简单的例子就可以显示，存在着多种配对不稳定的情况。我们把男孩们简称为α、β、γ、δ,假设这个例子里，α把β列在第一位，β把γ列在 第一位，γ把α列在第一位，而α、β、γ都把δ排在末位。不考虑δ的偏好，没办法安排稳定的配对，因为，被安排跟δ一个宿舍的那个男孩会想要搬出去，而其 他两个男孩中的一个男孩，会愿意接纳这个搬出的男孩搬进自己的宿舍。
上面提到的这些例子都说明，要找到解决稳定配对的方案不那么容易，不过，可以得出两个定理。
定理一，总存在稳定的婚姻配对。
证据。我们将通过递次求近法证明稳定婚姻配对的存在，找到一个稳定的婚姻配对。
首先，让每个男子向自己最喜欢的女子求婚，每个收到不止一个求婚的女子，可以从求婚者中选出自己最喜欢的一个，并且拒绝其他求婚者。但是，这个女子并不立刻接受当下最喜欢的求婚者的求婚，而是将他作为保留人选，给下一轮求婚者中更好的人选机会。
然后，进入第二个阶段，在第一轮求婚中被拒绝的男子，可以向自己的第二选择求婚。收到求婚的女子，从新的求婚者和保留的求婚者中，选出自己最喜欢的求婚者，同样，再次拒绝其他求婚者，只保留自己最喜欢的求婚者。
接下来，以同样的方式继续。在第二阶段被拒绝的求婚者，向自己的次一个选择求婚，女子仍然只从保留的求婚者和新的求婚者中选出最喜欢的人，拒绝掉其他人。
最终（实际上，最多经过n2-2n+2个阶段），每个女子都会收到一个求婚，因为只要有一个女子还没有被求婚，就存在拒绝和新一轮求婚，不过，因为没有男子能够对同一个女子提出超出一次求婚，每个女子总会在适当的时候得到一个求婚。当每个女子都收到求婚时，“求婚”行动就结束了。这时，每个女子 都要接受自己保留的那个求婚者。
我们相信这种婚姻配对是稳定的。比如，约翰和玛丽没有能结婚，而约翰喜欢玛丽胜过自己的妻子。那么，约翰肯定在过去某个时刻向玛丽求过婚，而玛丽当时因为更喜欢别人拒绝了约翰。很明显，玛丽肯定喜欢自己的丈夫胜过约翰。也就不存在婚姻的不稳定。
读者可能自娱自乐一下，把这个例证的程序应用到解决例1和例2上。
稳定配对，也不一定非得要求有一样数量的男子和女子。假设有b个男子，g个女子，如果bg，当每个男子要么被某个女子作为了保留人选，要么被所有女子拒绝了的时候，这个过程结束。这两种情况下的婚姻配对都是稳定的。
显然，存在一个完全对称的程序，即如果女子向男子求婚，也会达成稳定的婚姻配对。然而，如果男子求婚，配对的结果对男子来说最好，如果女子求婚，配对的结果会对女子来说最好。只有当存在唯一的稳定婚姻配对时，两种程序的分配结果才会一样。
稳定分配和入学问题
将“延迟接受”的程序延伸到大学入学问题。方便起见，假定如果一个学校在任何情况下都不愿意招收某个学生，这个学生甚至不被允许申请这个学校。
在这个前提下，我们来理解下面的程序：首先，所有的学生都向自己的首选学校提出申请。一个有q个招生名额的学校，将排在前面的q个学生放进自己 的候补名单，而拒绝其他申请者。如果给这个学校提出申请的学生人数不满q人，这个学校将所有申请者都列入候补名单。被这个学校拒绝的申请者，向自己的第二选择学校提出申请，再次，每个学校都从新的申请者和自己的候补名单中选出q个申请者，将这些学生建立一个新的候补名单，同样，拒绝掉其他申请者。
当每个申请者要么在某个候补名单上，要么被所有自己愿意去又被允许申请的学校拒绝时，这个程序就结束了。这个时候，每个学校都接受各自候补名单上的所有申请者，稳定分配也就达成了。证实这种分配是稳定的，类似于证明根据这种方法进行的婚姻配对是稳定的，就留待读者自己验证吧。
最优解
现在，我们要说明，刚提到的“延迟接受”程序不仅可以让申请分配达到稳定，而且可以达到最优。
即定理二.每个申请者，至少觉得，经由延迟接受程序安排的分配带来的好处，跟其他稳定分配一样。
证据。如果有一种稳定分配把某个学生分配到某个学校，我们就把这个学校称作对这个学生而言是“可能的”。这个证据要运用归纳法。假设，到程序中的某一个节点为止，没有申请学生被“可能的”学校拒绝。在这个节点上，假定学校A接到了满足招生名额的q个更具资格的申请者，因而拒绝了申请者α。我们必 须表明学校A对于申请者α而言，是“不可能”的。我们现在知道在A学校候补名单上的q个申请者，都喜欢A学校胜过其他学校，除了那些之前拒绝过他们因而对 他们而言“不可能”（假设）的学校。
设想一个分配方案，把申请者α送到A学校，把A学校候补名单上的申请者中的某一个送到其他可能接受他的学校。这样的话， 就要去到另一个他觉得 不如A学校的学校。这种分配是不稳定的，因为A学校很可能颠覆这种安排，换一种更利于双方的安排。所以说，这种设想的分配方案不稳定，A学校对于申请者α 而言，是“不可能”的。就此得出的结论是，我们的程序里，学校只是拒绝那些在任何稳定分配方案中都不会被录取的学生，因而，我们程序所得出的分配结果是最佳的。
我们顺带也注意到，尽管在这个案例里面，不会遇到婚姻配对时的对称问题。然而，也可以反转入学模式，来达到唯一的“入学最优”分配。这种反转的方法有点像联谊会的“高峰周”，首先，每个学校竞标自己最中意的那些学生，一直到自己的招生名额满了，然后，被竞标的学生保留最具吸引力的学校，拒绝掉其他学校，等等。
结论
阅读至此的读者无疑会注意到我们讨论的特点。为了对我们的问题进行数学分析，我们进行了所需的特定假设，从开始的大学入学问题，到最后讨论婚姻配对问题，我们都抛弃了现实，进入了一个理想化的数学世界。
务实的读者大概会马上问，我们有没有做一些努力，来解决现实中的问题。虽然，要回答这个问题，需要考虑许多非数学的因素，而且这种讨论在数学期刊上似乎不太适宜，我们的观点是，我们在这里介绍的观点，可能会被利用于解决某个阶段的入学问题。
最后，我们注意一下前文分析的另一个方面，这可能对数学老师而言比较有趣。那就是，在我们的论述里，有大把的例子来反驳非数学家对数学的模式化看法。
多数数学家很可能会在某些时候，觉得有必要反驳一下人们的一些固有观念，比如数学家“满脑子都是数据”或者数学家“知道很多公式”。在这些时候，如果随手有个例子可以证明数学不一定只关于数字或几何计算，应该会很方便。
出于此目的，我们推荐定理一的陈述和证明。我们讲述定理一并不是用各种数学符号，而是用普通的语言，并没有抽象或者技术性的术语，并不事先假定读者具有微积分知识。实际上，一般人也没有必要知道如何计算。虽然这样说，任何数学家还是能立马发现我们的论证是数学的，而没有受过数学训练的人们，尽管 对我们讨论的话题不陌生，仍可能觉得读懂我们的论证比较困难。
接下来，重提一个老问题，即：什么是数学？看起来，任何需要非常精确演算的论证都是数学的，我们的朋友和你们的朋友之所以不理解数学，不是因为他们没有数学头脑，而是因为跟上有些复杂的一连串推断，需要集中注意力到一定程度，他们做不到这一点。观察到这点，对于从事数学教学的人来说，不是什么新 鲜事。不过这点也许还没有被业界外的人们欣然接受，对他们来说，我刚提到的这些也许是一个有用的启发。
相关阅读：
作者：大卫·盖尔（David Gale）、罗伊德·S.沙普利（Harloy S. Shapley） ，译者：柯白玮。原文刊于1962年《美国数学月刊》第69卷，原文标题： “College Admissions and Stability of Marriges”。有兴趣的读者可点击以下“阅读原文”链接查阅原文。本文版权归属作者/译者/原载媒体。
有兴趣的读者敬请关注本号加入留学家长公益交流社群：